1. Field of the Invention
The present invention relates to image identification apparatus and methods of identifying images. More particularly the present invention relates to apparatus and methods for identifying images from hand drawn representations of the images.
2. Description of the Prior Art
There are many ways in which images may be created. Conventionally, an author or artist may draw a representation of the image using any appropriate means such as pencils, pens or other drawing equipment. An artist may also produce an image using a computer running a drawing application program which provides a facility for creating images and pictures by selecting pre-defined elements such as boxes, lines and circles which may be positioned, sized and shaped using a computer mouse. Furthermore to reduce a time required to generate an image, the computer may be provided with a library of pre-generated images which may be selected and copied into a picture to produce a desired scene. The images may be for example parts of or complete pictures, designs for articles or representations of a scene of a play, television programme or film.
In the field of character recognition, images representing characters from an alphabet are recognised and the character from this alphabet is generated in response to input representations of those characters. An example of this is provided in a disclosure entitled xe2x80x9cNeural Network Classifiers for Optical Chinese Character Recognitionxe2x80x9d by R. Romero, R. Berger, R. Thibadeau and D. Touretsky of the Imaging Systems Lab., Robotics Institute, Carnegie Mellon University published on the Internet at http://www-cgi.cs.cmu.edu. Furthermore the input representations may be hand drawn. In this case to assist in identifying the image, the hand drawn representation may be segmented into a number of different strokes of a pen which were performed in drawing the representation. This is disclosed in an article entitled xe2x80x9cPen-tip velocity in Handwritingxe2x80x9d, published on the Internet at http://hwr.nici.kun.nl/recog/hwr-tutor/veocity.html, copyright Lambert Schomaker, Apr. 1, 1996.
Generally it is desirable to provide a facility for generating an image from a hand drawn representation of the image in an efficient manner. This is appropriate, for example, during early stages of expressing ideas and initial thoughts for a picture. design or scene, where creative ideas are readily expressed as hand drawn representations.
According to the present invention there is provided an image identification apparatus for identifying an image from a sequence of spatial samples generated in response to a hand drawn representation of the image, the image identification apparatus comprising a segment processor arranged in operation to determine from the spatial samples stroke data representative of strokes performed in drawing the hand drawn representation of the image, a stroke pre-processor which is arranged in operation to generate parameter data from the sequence of spatial samples and the determined stroke data of the hand drawn representation, and an image identifier coupled to the stroke pre-processor which is arranged in operation to identify the image from the parameter data.
It is known that a drawing processor may be arranged in use to produce a sequence of spatial samples in response to a hand drawn representation of an image. However recognising an image from the spatial samples presents a technical problem for an image identifier. By providing a segment processor which operates to receive the spatial samples and to determine from the spatial samples stroke data corresponding to the strokes which were used in drawing the hand drawn representation of the image, a set of data produced by combining the stroke data with the spatial samples from which an image may be identified is substantially reduced with respect to a data set formed from the spatial samples alone. Thus an image can be more easily identified from the smaller data set formed by combining the stroke data with the spatial samples. The number of strokes performed in creating the hand drawn representation which may be included in the stroke data provides an indication of the image. For example, a triangle will consist of three strokes, whereas a square will consist of four strokes.
The stroke pre-processor produces the parameter data which represents the data set from which the image may be identified. The stroke pre-processor therefore provides a particular advantage in that by combining the determined strokes with the spatial samples the data set produced is in a form in which a corresponding image can be more easily identified by the image identifier.
There are various ways in which a hand drawn representation may be created and from which a sequence of spatial samples representative of the image may be generated. The spatial samples are samples of the position of a drawing tool with reference to predetermined spatial co-ordinates. Although the image identification apparatus may receive a sequence of spatial samples which have been generated from some other means, preferably the image identification apparatus may include a drawing processor which may be connectable to a drawing tool for use in creating the hand drawn representation of the image, the sequence of spatial samples being generated in accordance with movement of the drawing tool.
The drawing processor may be any means by which the spatial samples may be produced from the hand drawn representation. Although the drawing processor generates spatial samples in response to the hand drawn representation of the image, there remains the requirement for accurately determining from the spatial samples the strokes which were performed in producing the hand drawn representation of the image. Advantageously, therefore the segment processor of preferred embodiments may be arranged to determine the stroke data by generating from the spatial samples relative direction information representative of a relative direction of the drawing tool, to determine from the relative direction information a number of changes of direction of the tool and to determine the strokes performed in creating the representation in accordance with the number changes in direction. To facilitate the detection of the number of changes of direction of the drawing tool, the segment processor may further operate to generate from the relative direction information a rate of change of direction of the tool and determine a number of peaks in the rate of change of direction of the tool, the number of peaks being indicative of the number of changes of direction. To provide a further improvement in the confidence with which the stokes used to produce the hand drawn representation are detected, the segment processor may be provided with a filter through which the relative direction information may be passed, the number of times the tool changes direction being determined from the filtered relative direction information.
The spatial samples may be samples of the position of a drawing tool with reference to predetermined spatial co-ordinates. However the spatial samples may be provided with a temporal reference corresponding to a relative time at which the samples are generated. As such, the segment processor may in preferred embodiments operate to determine the strokes performed in creating the hand drawn representation by generating from the temporally referenced spatial samples relative speed information representative of a relative speed of the drawing tool with respect to time, determining from the relative speed information changes of speed of the tool, and determining the strokes of the hand drawn representation in accordance with the number of changes of speed. A further improvement in determining the number of strokes which are used to generate the hand drawn representation of the image may be provided by generating from the relative speed information a rate of change of the speed of the tool and identifying when the rate of change of speed reaches zero, the number of times the drawing tool changes speed being indicated from which of the identified zeros in the rate of change of speed corresponds to minimum speeds. To further improve a probability in correctly detecting and resolving the strokes used to generate the hand drawn representation of the image, the segment processor may have a filter through which the relative speed information is passed, the number of times the tool changes speed being determined from the filtered relative speed information.
A further improvement is provided in the probability of correctly detecting the strokes performed in drawing the hand drawn representation by combining the relative direction information and the relative speed information. Therefore by correlating the change in direction with the decreases in speed, a more accurate representation of the strokes performed in creating the hand drawn representation of the image is provided.
A particular advantage is provided in the process of identifying the image from the hand drawn representation by the stroke pre-processor which combines the identified strokes of the hand drawn representation with the spatial samples so that a data set defining the hand drawn representation is substantially reduced to that which would be required to define the image without providing the stroke pre-processor. In a preferred embodiment the stroke pre-processor may be arranged to determine a start and end point for each of the strokes, to form an outer boundary of the hand drawn representation from the start and end points of the strokes, to normalise the hand drawn representation from the outer boundary with respect to a pre-defined reference unit by proportionally adapting the spatial samples and to generate the stroke parameter data from the normalised hand drawn representation. By normalising the hand drawn representation with respect to the pre-defined reference unit, an image may be identified independently of a size which an artist may draw the image. In this way therefore an improvement is provided to the image identification apparatus in that the same image may be identified from different hand drawn representations of this image. This is particularly advantageous because different artists may draw images to different sizes, and furthermore the artist is not constrained to draw the image within a particular unit.
In a preferred embodiment the stroke parameter data may include at least one of a number of the strokes used to generate the hand drawn representation a centre of gravity of the hand drawn representation, a mean vector of the hand drawn representation, a normalised vector of the hand drawn representation, the length of the hand drawn representation and the balance of the hand drawn representation.
A further improvement to the image identification apparatus is afforded by arranging for the image processor to access a data store storing a plurality of images, and to indicate which of the plurality of images corresponds to the hand drawn representation of the image in accordance with the parameter data. Therefore although the image identifier may provide a reference indication of the image, an advantage is provided to the image identification apparatus by providing a data store which has a plurality of images pre-stored and from which the hand drawn representation of the image may be identified.
In a preferred embodiment the image identifier may be a neural network which is trained with stroke parameter data corresponding to the pre-stored images. More particularly, in a preferred embodiment the neural network may be a multi-layer perceptron, an input layer having a number of inputs corresponding to the number of stroke parameters formed from the parameter data, each of the stroke parameters being fed to a corresponding one of the layers.
In order to provide artists with an indication of the selected image, the image identifier may be arranged in operation to feed data representative of the indicated image to a visual display means connectable to the apparatus to provide a representation of the image.
The image identification apparatus may find application in several fields. However in a preferred embodiment, the image identification apparatus forms part of a story board production station, in which story boards for audio visual productions may be efficiently created from a set of pre-stored images.
According to a further aspect of the present invention there is provided a method of identifying an image from a sequence of spatial samples generated in response to a hand drawn representation of the image, the method comprising the steps of resolving, from the samples, strokes performed in creating the hand drawn representation of the image, generating parameter data by associating the spatial samples with the resolved strokes of the hand drawn representation, and identifying the image from the parameter data.
Further aspects and features of the present invention are provided and illustrated with reference to the appended claims.